package primary.code04_List;

import primary.util.ListUtils;

import java.util.Stack;

/**
 * 1->2->3->2->1，我们将它反转之后还是与原链表一样，就称这种链表结构为回文结构
 * 那么如何来判断一个链表它是不是回文链表呢？
 * <p>
 * 思路：
 * 1. 快慢指针找到中间点；
 * 2. 反准中间点之后的链表；
 * 3. 前后两个指针比较数据并向下移动，直到不同或null；
 * 4. 恢复链表
 */
public class Code03_PalindromeList {

    private static boolean isPalindromeList(Node head) {
        if (head == null || head.next == null) return false;
        Node slow = head;
        Node fase = head;
        while (fase.next != null && fase.next.next != null) {
            slow = slow.next;
            fase = fase.next.next;
        }
        Node reverseHead = reverseList(slow);
        Node end = reverseHead;
        while (head != null && end != null) {
            if (head.data != end.data) {
                reverseList(reverseHead);
                return false;
            }
            head = head.next;
            end = end.next;
        }
        reverseList(reverseHead);
        return true;
    }

    private static boolean isPalindromeListTest(Node head) {
        Node s = head;
        Node f = head;
        while (f.next != null && f.next.next != null) {
            f = f.next.next;
            s = s.next;
        }
        Node m = s;
        Node tail = reverseListTest(m);
        boolean res = true;
        while (head != null && tail != null) {
            if (head.data != tail.data) {
                res = false;
                break;
            }
            head = head.next;
            tail = tail.next;
        }
        reverseListTest(tail);
        return res;
    }

    private static Node reverseListTest(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node c = head;
        Node p = null;
        while (c != null) {
            Node n = c.next;
            c.next = p;
            p = c;
            c = n;
        }
        return p;
    }

    private static Node reverseList(Node head) {
        Node pre = null;
        Node cur = head;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private static boolean isPalindromeListByStack(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        for (int i = 0; i < stack.size(); i++) {
            if (cur.data != stack.pop().data) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    private static boolean isPalindromeListByReverse(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node s = head;
        Node f = head;
        while (f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
        }
        // 从中点开始反转
        Node pre = null;
        Node cur = s;
        while (cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        Node headReverse = pre; // 被反转的后半链表的头

        // 判断是否是回文
        Node p1 = head;
        Node p2 = pre;
        boolean result = true;
        while (p1 != null && p2 != null) {
            if (p1.data != p2.data) {
                result = false;
                break;
            } else {
                p1 = p1.next;
                p2 = p2.next;
            }
        }

        // 还原被反转的后半链表
        pre = null;
        cur = headReverse;
        while (cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return result;
    }

    private static Node reverseList0(Node head) {
        if (head == null || head.next == null) return head;
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            Node post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }

    /**
     * 原链表1：1-->2-->3-->3-->2-->1-->
     * true
     * 原链表1 test：1-->2-->3-->3-->2-->1-->
     * true
     * 原链表2：1-->2-->3-->
     * false
     * ==========
     * 原链表3：1-->2-->3-->
     * false
     * 原链表4：1-->2-->3-->
     */
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node31 = new Node(3);
        Node node4 = new Node(2);
        Node node5 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node31;
        node31.next = node4;
        node4.next = node5;
//        System.out.println("原链表1：" + ListUtils.printList(node1));
//        System.out.println(isPalindromeList(node1));
//
//        System.out.println("原链表1 test：" + ListUtils.printList(node1));
//        System.out.println(isPalindromeListTest(node1));
//
//        System.out.println("原链表2：" + ListUtils.printList(node1));
//        System.out.println(isPalindromeListByStack(node1));

        System.out.println("==========");
        System.out.println("原链表3：" + ListUtils.printList(node1));
        System.out.println(isPalindromeListByReverse(node1));
        System.out.println("原链表4：" + ListUtils.printList(node1));
    }
}
